Bounding shapes are shapes of at least two dimensions that contain part or all of at least one object and are often employed to accelerate the performance of, certain tests with respect to that which they contain. Bounding shapes are advantageous because they have simpler geometries than that which they contain and therefore simplify the tests. Common two-dimensional (2D) bounding shapes include bounding rectangles and circles. Three-dimensional (3D) bounding shapes are called bounding volumes and commonly include cuboids, spheres, ellipsoids, cylinders and slabs. The term, “bounding box,” includes both (2D) rectangles and (3D) cuboids. Bounding geometries may be used in combination, perhaps in a hierarchical tree structure, to contain objects having intricate geometries.
Bounding shapes may be used, for example, to perform collision detection, ray-intersection tests in the course of ray tracing, viewing-frustum tests in the course of graphics rendering and bounds compression for conservative rendering culling algorithms. As stated above, since a bounding shape necessarily encompasses that which it contains, if two bounding shapes do not collide, that which they contain cannot collide, and if a ray or viewing frustum does not intersect a bounding shape, it cannot intersect anything contained within the bounding shape.
An axis-aligned bounding box (AABB) is a hounding box (a rectangle or a cuboid) that is aligned with arbitrary axes extending from an origin in a given Cartesian coordinate system. An oriented bounding box (ORB) is a bounding box (a rectangle or a cuboid) that is aligned with an object it contains. In an N-dimensional coordinate system, a bounding box (either the AABB or OBB kind) is typically represented by N numbers indicating the position (e.g., the center) of the bounding box relative to the origin or an object it contains and N numbers indicating the size of the bounding box in each of its N dimensions (called the “extent”). In binary single-precision floating-point representation, each of the N numbers occupies 32 bits, or our bytes, resulting in total of 24 bytes to represent the bounding box in its entirety. It is common to employ tens of thousands of bounding boxes in a given context, so generating, manipulating and using hounding boxes to perform tests can consume significant computer processing and memory resources.